package selected;

import java.util.ArrayList;
import java.util.List;

public class J0825 {
    // 矩阵置零
    public void setZeroes(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        boolean row = false, col = false;

        // 遍历数组，将矩阵中为0的元素第一行和第一列置为0
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(matrix[i][j] == 0){
                    matrix[0][j] = 0;
                    matrix[i][0] = 0;
                    if(i == 0) row = true;
                    if(j == 0) col = true;
                }
            }
        }
        // 除第一行第一列外的元素置零
        for(int i = 1; i < m; i++){
            for(int j = 1; j < n; j++){
                if(matrix[i][0] == 0 || matrix[0][j] == 0){
                    matrix[i][j] = 0;
                }
            }
        }

        // 将第一行第一列置零
        if(row){
            for(int i = 0; i < m; i++){
                matrix[i][0] = 0;
            }
        }
        if(col){
            for(int j = 0; j < n; j++){
                matrix[0][j] = 0;
            }
        }
    }
    // 螺旋矩阵
    public List<Integer> spiralOrder(int[][] matrix) {
        int top = 0, bottom = matrix.length - 1, left = 0, right = matrix[0].length -1;
        List<Integer> ret = new ArrayList<Integer>();
        while(true){
            // 先遍历上边一行
            for(int i = left; i <= right; i++){
                ret.add(matrix[top][i]);
            }
            if(++top > bottom) break;
            for(int i = top; i <= bottom; i++){
                ret.add(matrix[i][right]);
            }
            if(--right < left) break;
            for(int i = right; i >= left; i--){
                ret.add(matrix[bottom][i]);
            }
            if(--bottom < top) break;
            for(int i = bottom; i >= top; i--){
                ret.add(matrix[i][left]);
            }
            if(++left > right) break;
        }
        return ret;
    }

    // 旋转矩阵
    public void rotate(int[][] matrix) {
        // 先按照主对角线进行翻转，再左右进行翻转
        int m = matrix.length, n = matrix[0].length;
        for(int i = 0; i < m; i++){
            for(int j = 0; j < i; j++){
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }

        for(int i = 0; i < m; i++){
            for(int j = 0; j < n / 2; j++){
                int temp = matrix[i][j];
                matrix[i][j] = matrix[i][n - 1- j];
                matrix[i][n - 1 - j] = temp;
            }
        }
    }
    // 搜索二维矩阵
    public boolean searchMatrix(int[][] matrix, int target) {
        // 从矩阵的右上角开始查找
        int i = 0, j = matrix[0].length - 1;
        while(i < matrix.length && j >= 0){
            if(matrix[i][j] == target){
                return true;
            } else if(matrix[i][j] > target){
                j--;
            } else {
                i++;
            }
        }
        return false;
    }
    // 相交链表
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lenA = 0, lenB = 0;
        ListNode curA = headA, curB = headB;
        while(curA != null){
            lenA++;
            curA = curA.next;
        }
        while(curB != null){
            lenB++;
            curB = curB.next;
        }
        int len = Math.abs(lenA - lenB);
        curA = headA; curB = headB;
        if(lenA > lenB){
            while(len-- > 0){
                curA = curA.next;
            }
        } else {
            while(len-- > 0){
                curB = curB.next;
            }
        }
        while(curA != null && curB != null){
            if(curA == curB){
                return curA;
            }
            curA = curA.next;
            curB = curB.next;
        }
        return null;
    }

    // 翻转链表
    public ListNode reverseList(ListNode head) {
        ListNode prev = null, cur = head;
        while(cur != null){
            ListNode curNext = cur.next;
            cur.next = prev;
            prev = cur;
            cur = curNext;
        }
        return prev;
    }

    // 回文链表
    public ListNode reverse(ListNode head){
        ListNode prev = null, cur = head;
        while(cur != null){
            ListNode curNext = cur.next;
            cur.next = prev;
            prev = cur;
            cur = curNext;
        }
        return prev;
    }
    public boolean isPalindrome(ListNode head) {
        int len = 0;
        ListNode cur = head;
        while(cur != null){
            cur = cur.next;
            len++;
        }
        cur = head;
        int i = len / 2;
        while(i-- > 0){
            cur = cur.next;
        }
        ListNode mid = cur.next;
        ListNode first = reverse(cur);
        if(len % 2 != 0) mid = mid.next;
        while(mid != null && first != null){
            if(mid.val == first.val){
                mid = mid.next;
                first = first.next;
            } else {
                return false;
            }
        }
        return true;
    }
    // 回文链表
    public ListNode reverse1(ListNode head){
        ListNode prev = null, cur = head;
        while(cur != null){
            ListNode curNext = cur.next;
            cur.next = prev;
            prev = cur;
            cur = curNext;
        }
        return prev;
    }
    public boolean isPalindrome1(ListNode head) {
        ListNode slow = head, fast = head, cur = head;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode mid = reverse1(slow);
        while(mid != null){
            if(mid.val == cur.val){
                mid = mid.next;
                cur = cur.next;
            } else {
                return false;
            }
        }
        return true;
    }
    public static void main(String[] args) {
        J0825 j0825 = new J0825();
        int[][] matrix = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
        j0825.rotate(matrix);
    }
}
